package leetcode_day._2022._202201._2131;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/1/21 10:19
 * 跳跃游戏 IV
 * 算法：广度优先搜索
 *
 */
public class _21_1345 {
    public static void main(String[] args) {
        System.out.println(new _21_1345().minJumps(new int[]{100, -23, -23, 404, 100, 23, 23, 23, 3, 404}));
    }

    static final int INF = 0x3f3f3f3f;
    public int minJumps(int[] arr) {
        int n = arr.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        // 倒序插入 list，相当于给 deque 增加一个同层「下标越大，优先出队」的作用
        for (int i = n - 1; i >= 0; i--) {
            final List<Integer> list = map.getOrDefault(arr[i], new ArrayList<>());
            list.add(i);
            map.put(arr[i], list);
        }
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(0);
        dist[0] = 0;
        while (!queue.isEmpty()) {
            int t = queue.pollFirst(), step = dist[t];
            if (t == n - 1) return step;
            if (t + 1 < n && dist[t + 1] == INF) {
                queue.addLast(t + 1);
                dist[t + 1] = step + 1;
            }
            if (t - 1 >= 0 && dist[t - 1] == INF) {
                queue.addLast(t - 1);
                dist[t - 1] = step + 1;
            }
            final List<Integer> list = map.getOrDefault(arr[t], new ArrayList<>());
            for (int ne : list) {
                if (dist[ne] == INF) {
                    queue.addLast(ne);
                    dist[ne] = step + 1;
                }
            }
            map.remove(arr[t]);
        }
        return -1;
    }

}
